#include <iostream>
#include <vector>

#include "TestCaseGenerator.h"

using namespace std;

void Swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

int Partition(vector<int> &array, int startIdx, int endIdx)
{
	int index = rand() % (endIdx - startIdx) + startIdx;
	int val = array[index];
	Swap(array[index], array[endIdx]);

	int smallIndex = startIdx;
	for (int i = startIdx; i < endIdx; i++)
	{
		if (array[i] < val)
		{
			if (smallIndex < i)
				Swap(array[i], array[smallIndex]);
			smallIndex++;
		}
	}
	Swap(array[smallIndex], array[endIdx]);
	return smallIndex;
}

void QuickSortWithIndex(vector<int> &array, int startIdx, int endIdx)
{
	if (endIdx - startIdx < 1)
		return;

	int index = Partition(array, startIdx, endIdx);
	if (index > startIdx)
		QuickSortWithIndex(array, startIdx, index - 1);
	if (index < endIdx)
		QuickSortWithIndex(array, index + 1, endIdx);
}

void QuickSort(vector<int> &array)
{
	int length = array.size();
	if (length <= 1)
		return;

	QuickSortWithIndex(array, 0, length - 1);
}


int main()
{
	shared_ptr<TestCaseGenerator> tcgPtr;

	vector<int> testCaseArray = tcgPtr->GenerateTestCase(20, 0, 100);
	cout << " Before sort: testCaseArray: " << endl;
	for each (int var in testCaseArray)
		cout << var << " ";
	cout << endl;
	QuickSort(testCaseArray);
	cout << " After sort: testCaseArray: " << endl;
	for each (int var in testCaseArray)
		cout << var << " ";
	cout << endl;

	vector<int> testCaseArray1 = tcgPtr->GenerateTestCase();
	cout << " Before sort: testCaseArray1: " << endl;
	for each (int var in testCaseArray1)
		cout << var << " ";
	cout << endl;
	QuickSort(testCaseArray1);
	cout << " After sort: testCaseArray1: " << endl;
	for each (int var in testCaseArray1)
		cout << var << " ";
	cout << endl;
	

	return 0;
}